package com.ma.array.slidewindow;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * @ClassName SlideWindow
 * @Author: mayongqiang
 * @DATE 2022/3/21 12:33
 * @Description: 滑动窗口解决问题模板
 */
/*
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
    对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
    如果 s 中存在这样的子串，我们保证它是唯一的答案
 */
public class Solution76 {

    public static void main(String[] args) {
        /*
        输入：s = "ADOBECODEBANC", t = "ABC"
        输出："BANC
        输入: s = "a", t = "aa"
        输出: ""
        解释: t 中两个字符 'a' 均应包含在 s 的子串中，
        因此没有符合条件的子字符串，返回空字符串。
         */
        //System.out.println(slidingWindow("aa", "aa"));
        System.out.println(slidingWindow2("aa", "aa"));
    }

    /*
     * 1、我们在字符串S中使用双指针中的左右指针技巧，初始化left = right = 0，把索引左闭右开区间[left, right)称为一个「窗口」。
     *
     * 2、我们先不断地增加right指针扩大窗口[left, right)，直到窗口中的字符串符合要求（包含了T中的所有字符）。
     *
     * 3、此时，我们停止增加right，转而不断增加left指针缩小窗口[left, right)，直到窗口中的字符串不再符合要求（不包含T中的所有字符了）。
     *          同时，每次增加left，我们都要更新一轮结果。
     *
     * 4、重复第 2 和第 3 步，直到right到达字符串S的尽头。
     */
    public static String slidingWindow(String s, String t) {
        /*
        map存储的是字母和其对应的数字
        Mamet我们可以将其用数组替代
        下标表示该字母，对应数子表示该字母出现次数
         */
        // 字串与窗口内字符串对应的两个map
        HashMap<Character, Integer> need, window;
        need = new HashMap<>();
        window = new HashMap<>();
        // 将待搜寻的子字串存入need哈希表
        for (int i = 0; i < t.length(); i++) {
            need.put(t.charAt(i), need.getOrDefault(t.charAt(i), 0) + 1);
        }
        int left = 0, right = 0;
        int valid = 0;
        // 记录最小覆盖字串的起始索引及长度
        int start = 0, len = Integer.MAX_VALUE;
        while (right < s.length()) {
            // c 是将移入窗口的字符
            char c = s.charAt(right);
            // 右移窗口
            right++;
            // 进行窗口内数据的一系列更新
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).equals(need.get(c))) {
                    valid++;
                }
            }
            System.out.println("left:" + left + ",right:" + right);
            // 判断左侧窗口是否要更新
            while (valid == need.size()) {
                // 在这里更新最小覆盖字串
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                // d是将移出窗口的字符
                char d = s.charAt(left);
                // 左移窗口
                left++;
                // 进行窗口内数据的一系列更新
                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }

    public static String slidingWindow2(String s, String t) {
    /*
        map存储的是字母和其对应的数字
        Mamet我们可以将其用数组替代
        下标表示该字母，对应数子表示该字母出现次数
     */
        // 字串与窗口内字符串对应的两个map
        //HashMap<Character, Integer> need, window;
        int[] tCount = new int[128];
        int[] winCount = new int[128];
        char[] sChar = s.toCharArray();
        char[] tChar = t.toCharArray();

        ArrayList<Character> al = new ArrayList<>();    //创建一个数组集合
        for (int i = 0; i < t.length(); i++) {        //循环遍历每一个字符
            if (!al.contains(tChar[i])) {                    //判断数组集合中是否有此字符，如果没有就添加到集合里面
                al.add(tChar[i]);            //添加到数组集合里面
            }
        }

        // 将待搜寻的子字串存入need哈希表
        for (int i = 0; i < t.length(); i++) {
            tCount[tChar[i]]++;
        }
        int left = 0, right = 0;
        int valid = 0;
        // 记录最小覆盖字串的起始索引及长度
        int start = 0, len = Integer.MAX_VALUE;
        while (right < s.length()) {
            // c 是将移入窗口的字符
            char c = sChar[right];
            // 右移窗口
            right++;
            // 进行窗口内数据的一系列更新
            if (tCount[c] > 0) {
                winCount[c]++;
                if (tCount[c] == winCount[c]) {
                    valid++;
                }
            }
            System.out.println("left:" + left + ",right:" + right);
            // 判断左侧窗口是否要更新
            while (valid == al.size()) {
                // 在这里更新最小覆盖字串
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                // d是将移出窗口的字符
                char d = sChar[left];
                // 左移窗口
                left++;
                // 进行窗口内数据的一系列更新
                if (tCount[d] > 0) {
                    if (winCount[d] == tCount[d]) {
                        valid--;
                    }
                    winCount[d]--;
                }
            }
        }
        return len == Integer.MAX_VALUE ? "##" : s.substring(start, start + len);
    }


}
